﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.ComponentModel;

namespace Sudoku
{
    public partial class SudokuControl : UserControl
    {
        private List<List<int>[,]> _lastValues;
        private SudokuSquare[,] _squares;
        private BackgroundWorker _worker;

        public SudokuControl()
        {
            InitializeComponent();

            _lastValues = new List<List<int>[,]>();
            _squares = new SudokuSquare[9, 9];
            for (int y = 8; y >= 0; y--)
            {
                for (int x = 8; x >= 0; x--)
                {
                    SudokuSquare ss = new SudokuSquare();
                    ss.HorizontalAlignment = System.Windows.HorizontalAlignment.Left;
                    ss.VerticalAlignment = System.Windows.VerticalAlignment.Top;
                    ss.Margin = new Thickness(x * 50, y * 50, 0, 0);
                    _squares[x, y] = ss;
                    this.LayoutRoot.Children.Insert(0, ss);
                }
            }

            for (int i = 1; i < 3; i++)
            {
                Line l1 = new Line();
                l1.X1 = 0;
                l1.X2 = 450;
                l1.Y1 = i * 150;
                l1.Y2 = i * 150;
                l1.Stroke = new SolidColorBrush(Colors.Black);
                l1.StrokeThickness = 4;
                this.LayoutRoot.Children.Add(l1);

                Line l2 = new Line();
                l2.X1 = i * 150;
                l2.X2 = i * 150;
                l2.Y1 = 0;
                l2.Y2 = 450;
                l2.Stroke = new SolidColorBrush(Colors.Black);
                l2.StrokeThickness = 4;
                this.LayoutRoot.Children.Add(l2);
            }

            _worker = new BackgroundWorker();
            _worker.DoWork += new DoWorkEventHandler(_worker_DoWork);
            _worker.RunWorkerCompleted += new RunWorkerCompletedEventHandler(_worker_RunWorkerCompleted);
        }

        void _worker_DoWork(object sender, DoWorkEventArgs e)
        {
            Solve();
        }

        void _worker_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            for (int y = 0; y < 9; y++)
            {
                for (int x = 0; x < 9; x++)
                {
                    _squares[x, y].Update();
                }
            }
        }

        public void BeginSolve()
        {
            _worker.RunWorkerAsync();
        }

        private void Solve()
        {
            Save();

            bool hasChanged = true;
            while (hasChanged)
            {
                while (hasChanged)
                {
                    hasChanged = false;
                    for (int y = 0; y < 9; y++)
                    {
                        for (int x = 0; x < 9; x++)
                        {
                            if (_squares[x, y].PossibleValues.Count != 1)
                            {
                                List<int> possibleValues = GetPossibleValues(x, y).ToList();
                                if (possibleValues.Count != 0 && (_squares[x, y].PossibleValues.Count == 0 ||
                                    possibleValues.Count < _squares[x, y].PossibleValues.Count))
                                {
                                    hasChanged = true;
                                    _squares[x, y].PossibleValues = possibleValues;
                                }
                            }
                        }
                    }
                }

                for (int y = 0; y < 9; y++)
                {
                    if (!hasChanged)
                    {
                        List<int> squareXs = new List<int>();
                        List<int> squareValues = new List<int>();
                        CheckForUniqueValuesInRow(y, out squareXs, out squareValues);
                        for (int i = 0; i < squareXs.Count; i++)
                        {
                            hasChanged = true;
                            _squares[squareXs[i], y].PossibleValues.Clear();
                            _squares[squareXs[i], y].PossibleValues.Add(squareValues[i]);
                        }
                    }
                }

                for (int x = 0; x < 9; x++)
                {
                    if (!hasChanged)
                    {
                        List<int> squareYs = new List<int>();
                        List<int> squareValues = new List<int>();
                        CheckForUniqueValuesInRow(x, out squareYs, out squareValues);
                        for (int i = 0; i < squareYs.Count; i++)
                        {
                            hasChanged = true;
                            _squares[x, squareYs[i]].PossibleValues.Clear();
                            _squares[x, squareYs[i]].PossibleValues.Add(squareValues[i]);
                        }
                    }
                }

                for (int y = 0; y < 3; y++)
                {
                    for (int x = 0; x < 3; x++)
                    {
                        if (!hasChanged)
                        {
                            List<Point> squares = new List<Point>();
                            List<int> squareValues = new List<int>();
                            CheckForUniqueValuesInSquare(x * 3, y * 3, out squares, out squareValues);
                            for (int i = 0; i < squares.Count; i++)
                            {
                                hasChanged = true;
                                Point p = squares[i];
                                _squares[(int)p.X, (int)p.Y].PossibleValues.Clear();
                                _squares[(int)p.X, (int)p.Y].PossibleValues.Add(squareValues[i]);
                            }
                        }
                    }
                }
            }

            if (!IsDone())
            {
                for (int y = 0; y < 9; y++)
                {
                    for (int x = 0; x < 9; x++)
                    {
                        if (_squares[x, y].PossibleValues.Count == 2)
                        {
                            int temp = _squares[x, y].PossibleValues[0];
                            _squares[x, y].PossibleValues.RemoveAt(0);
                            Solve();
                            if (!Check(false))
                            {
                                Load(false);
                                _squares[x, y].PossibleValues.RemoveAt(0);
                                _squares[x, y].PossibleValues.Add(temp);
                                Solve();
                                if (!Check(false))
                                {
                                    Load(false);
                                }
                                return;
                            }
                            else
                            {
                                return;
                            }
                        }
                    }
                }
            }
        }

        private void Save()
        {
            List<int>[,] values = new List<int>[9, 9];
            for (int y = 0; y <= _squares.GetUpperBound(1); y++)
            {
                for (int x = 0; x <= _squares.GetUpperBound(0); x++)
                {
                    values[x, y] = new List<int>();
                    foreach (int n in _squares[x, y].PossibleValues)
                    {
                        values[x, y].Add(n);
                    }
                }
            }
            _lastValues.Add(values);
        }

        private void Load(bool updateGui)
        {
            if (_lastValues.Count > 0)
            {
                List<int>[,] values = _lastValues[_lastValues.Count - 1];
                for (int y = 0; y <= _squares.GetUpperBound(1); y++)
                {
                    for (int x = 0; x <= _squares.GetUpperBound(0); x++)
                    {
                        _squares[x, y].PossibleValues.Clear();
                        foreach (int n in values[x, y])
                        {
                            _squares[x, y].PossibleValues.Add(n);
                        }
                        if (updateGui)
                        {
                            _squares[x, y].Update();
                        }
                    }
                }
                _lastValues.RemoveAt(_lastValues.Count - 1);
            }
        }

        public bool IsDone()
        {
            for (int y = 0; y < 9; y++)
            {
                for (int x = 0; x < 9; x++)
                {
                    if (_squares[x, y].PossibleValues.Count != 1)
                        return false;
                }
            }
            return true;
        }

        public bool Check(bool showInGui)
        {
            bool isOk = true;
            for (int y = 0; y < 9; y++)
            {
                for (int x = 0; x < 9; x++)
                {
                    if(showInGui)
                        _squares[x, y].textBox.Background = new SolidColorBrush(Colors.White);
                }
            }
            for (int x = 0; x < 9; x++)
            {
                if (!CheckColumn(x, showInGui))
                    isOk = false;
            }
            for (int y = 0; y < 9; y++)
            {
                if (!CheckRow(y, showInGui))
                    isOk = false;
            }
            for (int y = 0; y < 3; y++)
            {
                for (int x = 0; x < 3; x++)
                {
                    if (!CheckSquare(x, y, showInGui))
                        isOk = false;
                }
            }
            return isOk;
        }

        private bool CheckColumn(int x, bool showInGui)
        {
            bool isOk = true;
            List<int> timesDisplayed = new List<int>();
            List<Point> shownFrom = new List<Point>();
            for (int y = 0; y < 9; y++)
            {
                if (_squares[x, y].PossibleValues.Count == 1)
                {
                    if (!CheckSudokuSquare(x, y, timesDisplayed, shownFrom, showInGui))
                        isOk = false;
                }
            }
            if (!isOk && showInGui)
            {
                for (int y = 0; y < 9; y++)
                {
                    if (((SolidColorBrush)_squares[x, y].textBox.Background).Color != Color.FromArgb(128, 255, 0, 0))
                        _squares[x, y].textBox.Background = new SolidColorBrush(Colors.Red);
                }
            }
            return isOk;
        }

        private bool CheckRow(int y, bool showInGui)
        {
            bool isOk = true;
            List<int> timesDisplayed = new List<int>();
            List<Point> shownFrom = new List<Point>();
            for (int x = 0; x < 9; x++)
            {
                if (_squares[x, y].PossibleValues.Count == 1)
                {
                    if (!CheckSudokuSquare(x, y, timesDisplayed, shownFrom, showInGui))
                        isOk = false;
                }
            }
            if (!isOk && showInGui)
            {
                for (int x = 0; x < 9; x++)
                {
                    if (((SolidColorBrush)_squares[x, y].textBox.Background).Color != Color.FromArgb(128, 255, 0, 0))
                        _squares[x, y].textBox.Background = new SolidColorBrush(Colors.Red);
                }
            }
            return isOk;
        }

        private bool CheckSquare(int squareX, int squareY, bool showInGui)
        {
            bool isOk = true;
            List<int> timesDisplayed = new List<int>();
            List<Point> shownFrom = new List<Point>();
            for (int y = 0; y < 3; y++)
            {
                for (int x = 0; x < 3; x++)
                {
                    if (!CheckSudokuSquare(squareX * 3 + x, squareY * 3 + y, timesDisplayed, shownFrom, showInGui))
                        isOk = false;
                }
            }
            if (!isOk && showInGui)
            {
                for (int y = 0; y < 3; y++)
                {
                    for (int x = 0; x < 3; x++)
                    {
                        if (((SolidColorBrush)_squares[squareX * 3 + x, squareY * 3 + y].textBox.Background).Color != Color.FromArgb(128, 255, 0, 0))
                            _squares[squareX * 3 + x, squareY * 3 + y].textBox.Background = new SolidColorBrush(Colors.Red);
                    }
                }
            }
            return isOk;
        }

        private bool CheckSudokuSquare(int x, int y, List<int> timesDisplayed, List<Point> shownFrom, bool showInGui)
        {
            bool isOk = true;
            SudokuSquare ss = _squares[x, y];
            if (ss.PossibleValues.Count == 1)
            {
                int n = ss.PossibleValues[0];
                timesDisplayed.Add(n);
                shownFrom.Add(new Point(x, y));
                if (timesDisplayed.Where(num => num == n).Count() > 1)
                {
                    if (showInGui)
                    {
                        if(timesDisplayed.Contains(n))
                        {
                            Point firstPoint = shownFrom.ElementAt(timesDisplayed.IndexOf(n));
                            _squares[(int)firstPoint.X, (int)firstPoint.Y].textBox.Background = new SolidColorBrush(Color.FromArgb(128, 255, 0, 0));
                        }
                        ss.textBox.Background = new SolidColorBrush(Color.FromArgb(128, 255, 0, 0));
                    }
                    isOk = false;
                }
            }
            return isOk;
        }

        public void BackOne()
        {
            Load(true);
        }

        public void ClearTable()
        {
            for (int y = 0; y < 9; y++)
            {
                for (int x = 0; x < 9; x++)
                {
                    _squares[x, y].PossibleValues.Clear();
                    _squares[x, y].Update();
                    _squares[x, y].textBox.Background = new SolidColorBrush(Colors.White);
                }
            }
        }

        private IEnumerable<int> GetUniqueRowValues(int y)
        {
            for (int x = 0; x < 9; x++)
            {
                if (_squares[x, y].PossibleValues.Count == 1)
                    yield return _squares[x, y].PossibleValues[0];
            }
        }

        private IEnumerable<int> GetUniqueColumnValues(int x)
        {
            for (int y = 0; y < 9; y++)
            {
                if (_squares[x, y].PossibleValues.Count == 1)
                    yield return _squares[x, y].PossibleValues[0];
            }
        }

        private IEnumerable<int> GetUniqueSquareValues(int squareX, int squareY)
        {
            for (int y = squareY / 3 * 3; y < (squareY / 3 * 3) + 3; y++)
            {
                for (int x = squareX / 3 * 3; x < (squareX / 3 * 3) + 3; x++)
                {
                    if (_squares[x, y].PossibleValues.Count == 1)
                        yield return _squares[x, y].PossibleValues[0];
                }
            }
        }

        private void CheckForUniqueValuesInRow(int squareY, out List<int> squareXs, out List<int> squareValues)
        {
            squareXs = new List<int>();
            squareValues = new List<int>();
            int[] timesDisplayed = new int[10];
            int[] lastDisplayedFrom = new int[10];
            for (int x = 0; x < 9; x++)
            {
                if (_squares[x, squareY].PossibleValues.Count > 1)
                {
                    foreach (int n in _squares[x, squareY].PossibleValues)
                    {
                        timesDisplayed[n]++;
                        lastDisplayedFrom[n] = x;
                    }
                }
            }
            for(int i = 0; i < timesDisplayed.Length; i++)
            {
                if(timesDisplayed[i] == 1 && _squares[lastDisplayedFrom[i], squareY].PossibleValues.Count != 1)
                {
                    squareXs.Add(lastDisplayedFrom[i]);
                    squareValues.Add(i);
                }
            }
        }

        private void CheckForUniqueValuesInColumn(int squareX, out List<int> squareYs, out List<int> squareValues)
        {
            squareYs = new List<int>();
            squareValues = new List<int>();
            int[] timesDisplayed = new int[10];
            int[] lastDisplayedFrom = new int[10];
            for (int y = 0; y < 9; y++)
            {
                if (_squares[squareX, y].PossibleValues.Count > 1)
                {
                    foreach (int n in _squares[squareX, y].PossibleValues)
                    {
                        timesDisplayed[n]++;
                        lastDisplayedFrom[n] = squareX;
                    }
                }
            }
            for(int i = 0; i < timesDisplayed.Length; i++)
            {
                if (timesDisplayed[i] == 1 && _squares[squareX, lastDisplayedFrom[i]].PossibleValues.Count != 1)
                {
                    squareYs.Add(lastDisplayedFrom[i]);
                    squareValues.Add(i);
                }
            }
        }

        private void CheckForUniqueValuesInSquare(int squareX, int squareY, out List<Point> squares, out List<int> squareValues)
        {
            squares = new List<Point>();
            squareValues = new List<int>();
            int[] timesDisplayed = new int[10];
            Point[] lastDisplayedFrom = new Point[10];
            for (int y = squareY / 3 * 3; y < (squareY / 3 * 3) + 3; y++)
            {
                for (int x = squareX / 3 * 3; x < (squareX / 3 * 3) + 3; x++)
                {
                    foreach (int n in _squares[x, y].PossibleValues)
                    {
                        timesDisplayed[n]++;
                        lastDisplayedFrom[n] = new Point(x, y);
                    }
                }
            }
            for (int i = 0; i < timesDisplayed.Length; i++)
            {
                if (timesDisplayed[i] == 1 && _squares[(int)lastDisplayedFrom[i].X, (int)lastDisplayedFrom[i].Y].PossibleValues.Count != 1)
                {
                    squares.Add(lastDisplayedFrom[i]);
                    squareValues.Add(i);
                }
            }
        }

        //private int GetSudokuSquareValues(int x, int y)
        //{
        //    if (_squares[x, y].PossibleValues.Count == 1)
        //    {
        //        yield return _squares[x, y].PossibleValues[0];
        //    }
        //    else
        //    {
        //        foreach (int n in _squares[x, y].PossibleValues)
        //        {
        //            yield return n;
        //        }
        //    }
        //}

        private IEnumerable<int> GetPossibleValues(int squareX, int squareY)
        {
            if (_squares[squareX, squareY].PossibleValues.Count != 1)
            {
                IEnumerable<int> impossibleValues = GetImpossibleValues(squareX, squareY).Distinct();
                List<int> allPossibleValues = new List<int>();
                for (int i = 1; i <= 9; i++)
                {
                    if (!impossibleValues.Contains(i))
                    {
                        allPossibleValues.Add(i);
                    }
                }
                return allPossibleValues;
            }
            return null;
        }

        private IEnumerable<int> GetImpossibleValues(int x, int y)
        {
            return GetUniqueRowValues(y).Concat(GetUniqueColumnValues(x)).Concat(GetUniqueSquareValues(x, y)).Distinct();
        }

        private void UserControl_KeyDown(object sender, KeyEventArgs e)
        {

        }
    }
}
